package com.wenhao.netease.internet;

import org.junit.Test;

import javax.swing.plaf.basic.BasicInternalFrameTitlePane;
import java.util.concurrent.CountDownLatch;

public class Main4 {
    @Test
    public void test() {
        System.out.println(minSailCost(new int[][]{
                {1,1,1,1,0},{0,1,0,1,0},{1,1,2,1,1},{0,2,0,0,1}
        }));
    }
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 计算最小航行费用
     * @param input int整型二维数组 二维网格
     * @return int整型
     */
    public int minSailCost (int[][] input) {
        // write code here
        visited = new int[input.length][input[0].length];
        cost = new int[input.length][input[0].length];
        dfs(0,0,0,input);
        int temp;
        if ((temp = cost[input.length - 1][input[0].length - 1]) == Integer.MAX_VALUE) {
            return -1;
        }
        return temp - input[0][0];
    }

    private int[][] visited;
    private int[][] cost;

    public int dfs (int x,int y,int path,int[][] input) {
        if (input[x][y] == 2) {
            cost[x][y] = Integer.MAX_VALUE;
            return cost[x][y];
        } else {
            path += 2 - input[x][y];
        }
        if (x == visited.length - 1 && y == visited[0].length - 1) {
            if (cost[x][y] == 0) {
                cost[x][y] = path;
            } else {
                cost[x][y] = path < cost[x][y] ? path : cost[x][y];
            }
            return path;
        }
        visited[x][y] = 1;
        if (x - 1 > -1 && visited[x - 1][y] == 0) {
            int temp = dfs(x - 1,y,path,input);
            if (cost[x][y] == 0) {
                cost[x][y] = temp;
            } else {
                cost[x][y] = temp < cost[x][y] ? temp : cost[x][y];
            }
        }
        if (y - 1 > -1 && visited[x][y - 1] == 0) {
            int temp = dfs(x,y - 1,path,input);
            if (cost[x][y] == 0) {
                cost[x][y] = temp;
            } else {
                cost[x][y] = temp < cost[x][y] ? temp : cost[x][y];
            }
        }
        if (x + 1 < input.length && visited[x + 1][y] == 0) {
            int temp = dfs(x + 1,y,path,input);
            if (cost[x][y] == 0) {
                cost[x][y] = temp;
            } else {
                cost[x][y] = temp < cost[x][y] ? temp : cost[x][y];
            }
        }
        if (y + 1 < input[0].length && visited[x][y + 1] == 0) {
            int temp = dfs(x,y + 1,path,input);
            if (cost[x][y] == 0) {
                cost[x][y] = temp;
            } else {
                cost[x][y] = temp < cost[x][y] ? temp : cost[x][y];
            }
        }
        visited[x][y] = 0;
        return cost[x][y];
    }
}
